package com.eddie.tenalgorithm.binarysearchnorecursion;

/**
 * @author Eddie
 * @date 2022/08/15 16:01
 **/
public class BinarySearchNoRecur {
    public static void main(String[] args) {
        int[] arr = {1, 3, 8, 10, 11, 67, 100};
        int i = binarySearch(arr, -1);
        System.out.println(i);
    }

    /**
     * 二分查找的非递归实现
     * 说明：
     * 1、如果{1, 3, 8, 10, 11, 67, 100};里查找数字8
     * 2、默认设置right = 6
     * 3、mid = (left +right) / 2 => 3
     * 4、arr[3] = 11; 比8大，设置right = mid -1 => 2
     * 5、新一轮循环，mid = left + right = 2
     * 6、arr[2] == target；直接返回
     *
     * @param arr    待查找的数组
     * @param target 需要查找的数
     */
    public static int binarySearch(int[] arr, int target) {
        //定义左指针默认为0
        int left = 0;
        //定义右指针默认为数组长度-1
        int right = arr.length - 1;
        //如果左指针小于等于右指针代表可以查找
        while (left <= right) {
            //左右指针之和/2为中间指针
            int mid = (left + right) / 2;
            //如果arr[mid] 匹配就直接返回mid
            if (arr[mid] == target) {
                return mid;
                //中间数比目标数大
            } else if (arr[mid] > target) {
                //需要向左查找,右指针设置为中间索引-1，下一次循环新的mid = 就是0+（现在mid-1）的值
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}
